#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int i = 2; i <= n; i += 2) {
            if (p[i - 1] == '*') dp[0][i] = true;
            else break;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (p[j - 2] == '.' || p[j - 2] == s[i - 1]) && dp[i - 1][j];
                }
                else {
                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '.') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;
        s1 = " " + s1, s2 = " " + s2, s3 = " " + s3;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (s2[i] == s3[i])
                dp[0][i] = true;
            else break;
        }
        for (int j = 1; j <= m; ++j) {
            if (s1[j] == s3[j])
                dp[j][0] = true;
            else break;

        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j])
                    || (s2[j] == s3[i + j] && dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int left = newInterval[0], right = newInterval[1];
        vector<vector<int>> ret;
        bool placed = false;
        for (auto e : intervals) {
            if (e[0] > right) {
                if (!placed) {
                    ret.push_back({ left,right });
                    placed = true;
                }
                ret.emplace_back(e);
            }
            else if (e[1] < left) {
                ret.emplace_back(e);
            }
            else {
                left = min(e[0], left);
                right = max(e[1], right);
            }
        }
        if (!placed)
            ret.push_back({ left,right });
        return ret;
    }

    int totalNQueens(int n) {
        return dfs(n, 0, 0, 0, 0);
    }
    int dfs(int n, int pos, int col, int diag1, int diag2) {
        if (n == pos) return 1;
        int count = 0;
        int av = ((1 << n) - 1) & (~(col | diag1 | diag2));
        while (av != 0) {
            int position = av & (-av);
            av = av & (av - 1);
            count += dfs(n, pos + 1, col | position, (diag1 | position) << 1, (diag2 | position) >> 1);
        }
        return count;
    }
};